A Refined Harmonic Lanczos Bidiagonalization Method and an Implicitly Restarted Algorithm for Computing the Smallest Singular Triplets of Large Matrices

摘要

The harmonic Lanczos bidiagonalization method can be used to compute thesmallest singular triplets of a large matrix $A$. We prove that for good enoughprojection subspaces harmonic Ritz values converge if the columns of $A$ arestrongly linearly independent. On the other hand, harmonic Ritz values may misssome desired singular values when the columns of $A$ almost linearly dependent.Furthermore, harmonic Ritz vectors may converge irregularly and even may failto converge. Based on the refined projection principle for large matrixeigenproblems due to the first author, we propose a refined harmonic Lanczosbidiagonalization method that takes the Rayleigh quotients of the harmonic Ritzvectors as approximate singular values and extracts the best approximatesingular vectors, called the refined harmonic Ritz approximations, from thegiven subspaces in the sense of residual minimizations. The refinedapproximations are shown to converge to the desired singular vectors once thesubspaces are sufficiently good and the Rayleigh quotients converge. Animplicitly restarted refined harmonic Lanczos bidiagonalization algorithm(IRRHLB) is developed. We study how to select the best possible shifts, andsuggest refined harmonic shifts that are theoretically better than the harmonicshifts used within the implicitly restarted Lanczos bidiagonalization algorithm(IRHLB). We propose a novel procedure that can numerically compute the refinedharmonic shifts efficiently and accurately. Numerical experiments are reportedthat compare IRRHLB with five other algorithms based on the Lanczosbidiagonalization process. It appears that IRRHLB is at least competitive withthem and can be considerably more efficient when computing the smallestsingular triplets.